package com.lw.leetcode.str.b;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 842. 将数组拆分成斐波那契序列
 *
 * @Author liw
 * @Date 2021/6/29 16:02
 * @Version 1.0
 */
public class SplitIntoFibonacci {

    public static void main(String[] args) {
        SplitIntoFibonacci test = new SplitIntoFibonacci();
//        String str = "112358";
//        String str = "199100199";
//        String str = "1101111";
        String str = "101";

//        String str = "11235813213455890144";


        List<Integer> integers = test.splitIntoFibonacci(str);
        System.out.println(integers);

        // 121474836472147483648 true
        //     if(num.equals("0")) return false;
        //    if(num.equals("1")) return false;
        //    if(num.equals("10")) return false;
        //    if(num.equals("111")) return false;
        //    if(num.equals("113")) return false;
        //    if(num.equals("1023")) return false;
        //    if(num.equals("1203")) return false;
        //    if(num.equals("0235813")) return false;
        //    if(num.equals("199001200")) return false;
        //    if(num.equals("120122436")) return false;
        //    if(num.equals("121202436")) return false;
        //    if(num.equals("121224036")) return false;
        //    if(num.equals("19910011992")) return false;
        //    if(num.equals("1991000199299498797")) return false;
        //    if(num.equals("2461016264268110179")) return false;
        //    if(num.equals("11235813213455890144")) return false;

    }

    private List<Integer> list = new ArrayList<>();
    private char[] arr;
    private int length;

    public List<Integer> splitIntoFibonacci(String num) {

        if (num == null || num.length() < 3) {
            return Collections.emptyList();
        }
        length = num.length();
        arr = num.toCharArray();
        int b = length >> 1;
        int a1 = 0;
        int a2;
        for (int i = 0; i < b; i++) {
            a1 = a1 * 10 + arr[i] - 48;
            a2 = 0;
            if (i == 1 && arr[0] == '0') {
                return Collections.emptyList();
            }
            for (int j = i + 1; j < length; j++) {
                if (j > i + 1 && arr[i + 1] == '0') {
                    break;
                }
                a2 = a2 * 10 + arr[j] - 48;
                list = new ArrayList<>();
                list.add(a1);
                list.add(a2);
                if (find(a1, a2, j + 1)) {
                    return list;
                }
            }
        }
        return Collections.emptyList();
    }

    private boolean find(int a1, int a2, int st) {
        int add = a1 + a2;
        list.add(add);
        String str = String.valueOf(add);
        int l = str.length();
        if (st + l > this.length) {
            return false;
        }
        if (String.valueOf(arr, st, l).equals(str)) {
            if (st + l == this.length) {
                return true;
            }
            return find(a2, add, st + l);
        }
        return false;
    }


}
